#ifndef __LINKLINKIT__H__
#define __LINKLINKIT__H__

#include "Tipos.h"
#include "modulos/aed2/Lista.h"
#include "modulos/aed2/Arreglo.h"
#include "DiccTrie.h"
#include "ArbolCategorias.h"

/**
 * Implementación de LinkLinkIt.
 *
 * Implementación del LinkLinkIt del TP2.
 */
class LinkLinkIt {
	public:
		/**
		 * Crea un LinkLinkIt.
		 * @param[in] ac Árbol de categorías del sistema.
		 * @remark @b Complejidad: \f$\Theta(\#categorias(ac))\f$
		 * @remark @b Alias: Se guarda una referencia al árbol de categorías, por lo que no se debe destruir
		 *                   mientras lo esté utilizando el LinkLinkIt.
		 */
		LinkLinkIt( const ArbolCategorias &ac );

		/**
		 * Destruye un LinkLinkIt.
		 * @remark @b Complejidad: @f$\Theta(\#categorias + \#links \cdot |mayor~ link|)@f$, donde:
		 *         @li @b #categorias es la cantidad de categorías en el sistema.
		 *         @li @b \#links es la cantidad de links en el sistema.
		 *         @li @b |mayor @b link| está acotado por el largo del link más largo.
		 */
		~LinkLinkIt();

		/**
		 * Registra un nuevo link en el sistema.
		 * @param[in] link El link a registrar.
		 * @param[in] cat La categoría bajo la cual registrarlo.
		 * @pre @b link no puede ser uno de los links del LinkLinkIt.
		 * @pre @b cat tiene que ser una categoría válida del árbol de categorías del LinkLinkIt.
		 * @remark @b Complejidad: \f$\Theta(|link|+|cat|+altura(categorias(lli)))\f$, donde @b lli es el LinkLinkIt.
		 */
		void NuevoLink( const String &link, const String &cat );

		/**
		 * Registra un acceso a un link.
		 * @param[in] link El link al cual registrar el acceso.
		 * @param[in] fecha La fecha en la que se realizó el acceso.
		 * @pre @b link tiene que ser uno de los links registrados en el sistema.
		 * @pre @b fecha debe ser mayor o igual a la fecha actual del sistema.
		 * @remark @b Complejidad: \f$\Theta(|link|)\f$
		 */
		void Acceso( const String &link, Nat fecha );

		/**
		 * Devuelve la cantidad de links de una categoría y sus descendientes.
		 *
		 * Devuelve la cantidad de links que están registrados bajo una categoría o
		 * sus descendientes.
		 *
		 * @param[in] cat La categoría sobre la cual estamos realizando la consulta.
		 * @remark @b Complejidad: \f$\Theta(|cat|)\f$
		 * @returns La cantidad de links.
		 */
		Nat CantLinks( const String &cat );
	private:
		/**
		 * Representa un acceso a un link.
		 */
		struct accestr {
			bool valido; /**< @b true si ese acceso es válido. */
			Nat fecha; /**< La fecha de acceso al link. */
			Nat accesos; /**< La cantidad de accesos en dicha fecha. */
		};

		struct nodoCat;

		/**
		 * Nodo que representa un link.
		 */
		struct nodoLink {
			/** Constructor para nodoLink.
			 * @param[in] l Nombre del link.
			 * @parma[in] c Nombre de la categoría.
			 * @remark @b Complejidad: @f$\Theta(|l|+|c|)@f$
			 */
			nodoLink( const String &l, const String &c ) {
				nombre = l;
				cat = c;
				for ( int i = 0; i < 3; i++ ) {
					accesos[i].fecha = 0;
					accesos[i].accesos = 0;
					accesos[i].valido = false;
				}
				categoria = NULL;
			}
			String nombre; /**< Nombre del link. */
			String cat; /**< Nombre de la categoría. */
			nodoCat *categoria; /**< Puntero al nodo de la categoría. */
			accestr accesos[3]; /**< Las 3 últimas fechas de acceso al link. */
		};

		/**
		 * Nodo que representa una categoría
		 */
		struct nodoCat {
			/**
			 * Constructor del nodo.
			 * @remark @b Complejidad: @f$\Theta(1)@f$
			 */
			nodoCat() {
				padre = NULL;
				version = 0;
				total = 0;
				ultimaFecha = 0;
			}
			nodoCat *padre; /**< Puntero al nodo de la categoría padre. */
			Nat version; /**< Versión de la categoría (utilizado por el constructor del iterador). */
			Nat total; /**< Total de links en la categoría (propios y de sus descendientes). */
			Nat ultimaFecha; /**< Última fecha de acceso a un link de la categoría. */
			aed2::Lista<nodoLink *> links; /**< Lista de punteros a nodos de links en la categoría y sus descendientes. */
		};

		DiccTrie<nodoLink *> links; /**< Diccionario con todos los links del sistema. Los links son las claves. */
		aed2::Arreglo<nodoCat *> cats; /**< Arreglo con todas las categorías del sistema. El id de cada categoría es la clave. */
		const ArbolCategorias &ac; /**< Referencia no modificable al árbol de categorías del sistema. */
		Nat fechaActual; /**< La fecha actual del sistema (última fecha de acceso a algún link). */
		Nat version; /**< La versión del sistema (utilizada para acelerar la construcción de iteradores). */

		/**
		 * Agrega una categoría al sistema.
		 * Esta función se utiliza durante la construcción del LinkLinkIt.
		 * A medida que se recorre un iterador del árbol de categorías se van
		 * agregando las categorías de éste.
		 * @param[in] e Categoría a agregar.
		 * @remark @b Complejidad: @f$\Theta(1)@f$
		 */
		void AgregarCategoria( const ArbolCategorias::Iterador::ItElem &e );

		/**
		 * Agrega los hijos de una categoría al sistema.
		 * Esta función se utiliza durante la construcción del LinkLinkIt.
		 * A medida que se recorre un iterador del árbol de categorías se van
		 * agregando los hijos del elemento actual (it.Siguiente()) al sistema.
		 * @param[in] it Iterador que apunta al elemento del cual agregar sus hijos.
		 * @pre it.HayMas()
		 * @remark @b Complejidad: @f$\Theta(\#hijos)@f$, donde @b #hijos es la cantidad de categorías
		 *         por debajo de @b it.Siguiente()
		 */
		void AgregarHijos( const ArbolCategorias::Iterador &it );

		/**
		 * Selecciona la fecha a modifcar de un nodoLink.
		 * @param[in] nl Puntero al nodoLink sobre el cual trabajar.
		 * @param[in] fecha La fecha nueva.
		 * @pre fecha tiene que ser mayor o igual a la fecha actual del sistema.
		 * @remark @b Complejidad: @f$\Theta(1)@f$
		 * @returns Un índice dentro de los accesos del nodoLink que se puede modificar.
		 */
		Nat SeleccionarFechaAModificar( const nodoLink *nl, Nat fecha );
	
	public:
		/**
		 * Iterador de LinkLinkIt.
		 */
		class Iterador {
			public:
				/**
				 * Estructura devuelta por el iterador.
				 */
				struct ItElem {
					/**
					 * Constructor de la estructura.
					 * @param[in] l Nombre del link.
					 * @param[in] c Nombre de la categoría.
					 * @param[in] ar Accesos recientes.
					 * @remark @b Alias: Se guarda una referencia constante a los argumentos @b l y @b c.
					 */
					ItElem( const String &l = "", const String &c = "", Nat ar = 0 )
						: link(l), categoria(c) { accesosRecientes = ar; }
					const String &link; /**< Nombre del link. */
					const String &categoria; /**< Nombre de la categoría. */
					Nat accesosRecientes; /**< Accesos recientes. */
				};

				/**
				 * Constructor del iterador.
				 * Al construir el iterador se pueden dar tres casos:
				 * @li No se modificó el sistema desde la última llamada al constructor,
				 *     este es el mejor caso, donde la complejidad es del orden de @f$\Theta(1)@f$.
				 * @li Se modificó el sistema pero la lista de links no sufre alteración
				 *     en el orden. Este caso tiene una complejidad del orden de @f$\Theta(n)@f$.
				 * @li La lista se encuentra totalmente desordenada, este es el peor caso, con una
				 *     complejidad del orden de @f$\theta(n^2)@f$.
				 *
				 * @param[in] lli Sistema.
				 * @param[in] categoria Categoría sobre la cual iterar.
				 * @remark @b Complejidad (peor caso): @f$\Theta(n^2)@f$
				 * @remark @b Complejidad (ya ordenado): @f$\Theta(n)@f$
				 * @remark @b Complejidad (mejor caso): @f$\Theta(1)@f$
				 */
				Iterador( const LinkLinkIt &lli, const String &categoria );

				/**
				 * Devuelve @b true si hay más elementos en el iterador.
				 */
				bool HayMas() const { return lista.HaySiguiente(); }

				/**
				 * Devuelve el siguiente elemento.
				 */
				ItElem Siguiente() const;

				/**
				 * Avanza el iterador al siguiente elemento.
				 */
				void Avanzar() { lista.Avanzar(); }

			private:
				aed2::Lista<nodoLink *>::Iterador lista; /**< Iterador sobre el cual se construye el iterador. */
				Nat ultimaFecha; /**< Última fecha de la categoría. */


				/**
				 * Calcula los accesos recientes de un link.
				 * @param[in] fl Accesos recientes del link.
				 * @remark @b Complejidad: @f$\Theta(1)@f$
				 * @returns Los accesos recientes del link, en base al dato miembro @link LinkLinkIt::Iterador::ultimaFecha ultimaFecha
				 */
				Nat CalcularAccesosRecientes( const accestr fl[3] ) const;

				/**
				 * Ordena la lista de links en base a @link LinkLinkIt::Iterador::ultimaFecha ultimaFecha.
				 * @param[in] lista Lista de links a ordenar.
				 * @remark @b Complejidad (peor caso): @f$\Theta(n^2)@f$
				 * @remark @b Complejidad (mejor caso): @f$\Theta(n)@f$
				 */
				void Sort( aed2::Lista<nodoLink*> &lista ) const;
		};

		private:
			/**
			 * Libera la memoria ocupada por cada nodoLink en el diccionario de links.
			 * @param[in] nl Puntero al nodoLink del cual liberar la memoria.
			 */
			static void __liberar_dicctrie( nodoLink *&l ) { delete l; }
};

#endif
